#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;

#define in read()
#define pii pair<int,int>
#define fi first
#define se second
#define FILE(x) freopen(x".in","r",stdin);\
	freopen(x".out","w",stdout);
#define pb push_back

int read(){
	int x = 0,sgn = 1;char ch = getchar();
	for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;
	for(;isdigit(ch);ch = getchar()) x = (x<<1)+(x<<3)+(ch^48);
	return x*sgn;
}

const int MAXN = 1025;

int n,d,k[12];
ll f[MAXN][MAXN];
char s[12];
int main (){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	int T = in;
	while(T--){
		scanf("%s",s); n = strlen(s); for(int i = 0;i < n;i++) k[i] = s[i] ^ 48; d = in; sort(k,k+n);
		memset(f,0,sizeof(f)); f[0][0] = 1;
		for(int i = 0;i < 1 << n;i++)
			for(int j = 0;j < d;j++)
				if(f[i][j])
					for(int x = 0;x < n;x++)
						if(!(i>>x&1) && (x == 0 || ((i >> (x-1) & 1) || (k[x] != k[x-1])))){
							f[i|(1<<x)][(j*10+k[x])%d] += f[i][j];
						}
		ll ans = f[(1<<n)-1][0];
		printf("%lld\n",ans);
	}
	return 0;
}

